class code3 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>(wordDict);

        int n = s.length();

        //字符串[0-i]是否匹配
        boolean[] dp = new boolean[n+1];
        //初始化
        dp[0] = true;

        for(int i=1;i<=n;i++) {
            for(int j=i;j>0;j--) {
                if(dp[j-1]==true && hash.contains(s.substring(j-1,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}